package com.gitee.feizns.explore.data_structure.union_find;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * @author feizns
 * @since 2020/3/13
 */
public class SmallestStringWithSwaps {

    public static void main(String[] args) {
//        "qdwyt"
//                [[2,3],[3,2],[0,1],[4,0],[3,2]]
        System.out.println(smallestStringWithSwaps("qdwyt", Arrays.asList(
                Arrays.asList(2, 3),
                Arrays.asList(3, 2),
                Arrays.asList(0, 1),
                Arrays.asList(4, 0),
                Arrays.asList(3, 2)
        )));
    }

    public static String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        Uf uf = new Uf(s.length());
        for (List<Integer> pair : pairs)
            uf.union(pair.get(0), pair.get(1));
        Map<Integer, TreeMap<Character, Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            int m = uf.find(i);
            TreeMap<Character, Integer> map1 = map.get(m);
            if ( map1 == null )
                map1 = new TreeMap<>();
            Integer num = map1.get(s.charAt(i));
            if ( num == null )
                num = 0;
            map1.put(s.charAt(i), num + 1);
            map.put(m, map1);
        }

        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            TreeMap<Character, Integer> map1 = map.get(uf.find(i));
            Map.Entry<Character, Integer> entry = map1.pollFirstEntry();
            ret.append(entry.getKey());
            if ( entry.getValue() == 1 )
                map1.remove(entry.getKey());
            else
                map1.put(entry.getKey(), entry.getValue() - 1);
        }
        return ret.toString();
    }

    static class Uf {
        int[] parents;
        Uf(int size) {
            parents = new int[size];
            for (int i = 0; i < size; i++)
                parents[i] = i;
        }
        void union(int q, int p) {
            parents[find(q)] = find(p);
        }
        int find(int q) {
            if ( q != parents[q] )
                parents[q] = find(parents[q]);
            return parents[q];
        }
    }

}
